#include<iostream>

using namespace std;

#define root 1,n,1
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

const int maxn=100010;

struct rec
{
	int l,r;
	int square_sum,sum;
	int col;
	rec()
	{
		square_sum=sum=col=0;
	}
	rec(int ll,int rr,int v)
	{
		l=ll;r=rr;
		col=0;
		square_sum = v*v;
		sum=v;
	}
	void color(int v)
	{
		col += v;
		square_sum = square_sum + 2*v*sum + (r-l+1)*v*v;
		sum = sum + (r-l+1)*v;
	}
}z[maxn<<2];

rec operator+(rec a,rec b)
{
	rec c;
	c.l=a.l;c.r=b.r;
	c.square_sum = a.square_sum + b.square_sum;
	c.sum = a.sum + b.sum;
	return c;
}

void update(int rt)
{
	z[rt] = z[rt<<1] + z[rt<<1|1];
}

void color(int l,int r,int rt,int v)
{
	z[rt].color(v);
}

void push_col(int l,int r,int rt)
{
	if (z[rt].col != 0)
	{
		int m=(l+r)>>1;
		color(lson,z[rt].col);
		color(rson,z[rt].col);
		z[rt].col=0;
	}
}

void build(int l,int r,int rt)
{
	if (l==r)
	{
		z[rt] = rec(l,r,y[l]);
		return;
	}
	int m=(l+r)>>1;
	build(lson);
	build(rson);
	update(rt);
}

rec query(int l,int r,int rt,int nowl,int nowr)
{
	if (nowl<=l && r<=nowr) return z[rt];
	push_col(l,r,rt);
	int m=(l+r)>>1;
	if (nowl<=m)
	{
		if (m<nowr) return query(lson,nowl,nowr)+query(rson,nowl,nowr);
		else return query(lson,nowl,nowr);
	}
	else return query(rson,nowl,nowr);
}

void modify(int l,int r,int rt,int nowl,int nowr,int v)
{
	if (nowl<=l && r<=nowr)
	{
		color(l,r,rt,v);
		return;
	}
	push_col(l,r,rt);
	int m=(l+r)>>1;
	if (nowl<=m) modify(lson,nowl,nowr,v);
	if (m<nowr) modify(rson,nowl,nowr,v);
	update(rt);
}
